package main

func findNumberOfLIS(nums []int) int {
	dp := make([][2]int, len(nums)) // list of (maxLen, pathCount)
	for i := range nums {
		dp[i] = findLongest(dp, nums, i)
	}
	countMap := make(map[int]int) // len -> count
	maxLen := -1
	for _, v := range dp {
		l := v[0]
		pathCount := v[1]
		countMap[l] += pathCount
		if l > maxLen {
			maxLen = l
		}
	}
	return countMap[maxLen]
}

func findLongest(dp [][2]int, nums []int, index int) [2]int {
	max := 1
	maxCount := 1
	for i := 0; i < index; i++ {
		if nums[i] < nums[index] {
			if max < dp[i][0]+1 {
				max = dp[i][0] + 1
				maxCount = dp[i][1]
			} else if max == dp[i][0]+1 {
				maxCount += dp[i][1]
			}
		}

	}
	return [2]int{max, maxCount}
}

func main() {
	println(findNumberOfLIS([]int{1, 3, 5, 4, 7}))
}
